def BFS(Adj,s):
    n=len(Adj)
    d[s]=0
    pi[s]='source'
    q=deque()
    q.append(s)
    while len(q)!=0:
        u=q.popleft()
        for v in Adj[u]:
            if d[v]=='inf':
                d[v]=d[u]+1
                pi[v]=u
                q.append(v)

if __name__=='__main__':
    from collections import deque
    Adj=[[1,2],[0],[0,3],[2,4,5],[3,5,6],[3,4,6,7],[4,5,7],[5,6]]
    d=['inf']*len(Adj)
    pi=[None]*len(Adj)
    BFS(Adj,2)
    print Adj
    print d
    print pi
